package pers.vic.basics.algorithm.dp;

/**
 * @description:02.机器人走网格 动态规划
 * {@literal 62. 不同路径 https://leetcode-cn.com/problems/unique-paths/}
 * @date: 2020/11/12 0012 10:51
 * @author Vic.xu
 * @see A_01_frog  把一维数组变成二维数组
 */
public class A_02_uniquePaths_leetcode62 {
    /*
    一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
    机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
    问总共有多少条不同的路径？
     */

    /**
     * 经过了蛙跳{@link A_01_frog}的代码，我好像懂了一点动态规划的思路了
     * 1. 定义二维数组  dp[m][n] 标识移动到 m 和 n 位置可以的唯一路径数
     * 2. 找出关系：dp[m][n] = dp[m-1][n] + dp[m][n-1]+1  可以从上面下来，也可以是从左边过来
     * 3. 初始值：
     *   dp[0][0] = 0, 第一行和第二行都是1
     */
    public static int uniquePaths(int m, int n) {
        if (m <= 0 || n <= 0) {
            return 0;
        }
        int[][] dp = new int[m][n];
        //初始化第一行 和第一列
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                //可以从上面下来，也可以是从左边过来
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }

        return dp[m-1][n-1];
    }

    public static void main(String[] args) {
        System.out.println(uniquePaths(3, 2));
        System.out.println(uniquePaths(7, 3));
    }
}
